Особливості застосування методу мінімізації Квайна-Мак-Класкі-Петріка в базисі Буля. Метод отримання скороченої диз'юнктивної нормальної форми логічної функції називається методом Квайна. При мінімізації по методу Квайна в базисі 1 передбачається, що початкова функція задана в СНДФ. Нагадаємо, що імпліканта функції - це деяка логічна функція, що обертається в нуль при наборі змінних, на яких сама функція також рівна нулю. Тому будь-якої мінтерм у складі СНДФ, або групи мінтермов, сполучених знаками диз'юнкції, є імплікантамі початкової НДФ. Первинна або проста імпліканта функції - це імпліканта типу елементарної кон'юнкції деяких змінних, ніяка частина якої вже не є імплікантой даній функції. Диз'юнкція простих імплікант, жодну з яких виключити не можна, називається тупиковій НДФ заданій функції. Деякі функції мають декілька тупикових форм. Тупикові форми, що містять найменшу кількість букв, будуть мінімальними. Завдання мінімізації по методу Квайна полягає в попарному порівнянні всіх імплікант, що входять в СНДФ, з метою виявлення можливості поглинання якоїсь змінної: Fxi  Fxi = F. Таким чином, вдається понизити ранг термів. Ця процедура проводиться до тих пір, поки не залишиться жодного члена, що допускає поглинання з яким-небудь іншим термом. Терми, що піддалися поглинанню, наголошуються. Невідмічені терми є первинними імпліканти. Одержаний логічний вираз не завжди виявляється мінімальним. Тому досліджується можливість подальшого спрощення. Для цього складається таблиця, в рядках якої записуються знайдені первинні імпліканти, а в стовпцях указуються терми початкового рівняння. Клітки цієї таблиці наголошуються у випадку, якщо первинна імпліканта входить до складу якого-небудь терма. Після цього завдання спрощення зводиться до того, щоб знайти таку мінімальну кількість первинних імплікант, які покривають всі стовпці. У цьому методі використовуються операції неповного склеювання (повним склеюванням, як нам відомо, будет: xy  xy = x) і поглинання (x  xy = x). Вживана в методі Квайна операція неповного склеювання визначається формулою: xy  xy = x  xy  xy.. Відмітимо, що в правій частині рівності, окрім члена ч, одержаного в результаті повного склеювання, залишаються обидва члени, що беруть участь в склеюванні. Теорема Квайна. Якщо в довершеній диз'юнктивній нормальній формі логічної функції провести всі операції неповного склеювання і потім всі операції поглинання, то в результаті виходить скорочена диз'юнктивна нормальна форма цієї функції, тобто диз'юнкція всіх її простих імплікант. Метод Квайна виконується у декілька етапів і скорочену НДФ зручно знаходити в наступній послідовності. Провести в СНДФ функції всі можливі операції склеювання констітуєнт одиниці. В результаті цього утворюються твори, що містять (n - 1) букв. Підкреслимо, що склеюватися можуть тільки твори з однаковим числом букв. Тому після цієї процедури проводиться операція поглинання, а потім виконуються всі можливі склеювання членів з (n - 1) буквою. Після цього проводиться поглинання членів з (n - 1) буквою і знов виконується операція склеювання членів з числом букв, рівним (n - 2), і т.д. На підставі вищевикладеного сформулюємо алгоритм отримання мінімальних НДФ логічній функції. 1. Логічну функцію представляють в здійсненій НДФ, застосовуючи або запис "по одиницях" функції, якщо функція задана табличний, або застосовуючи операції розгортання, правила де Морганаї і інші формули алгебри логіки, якщо функція задана в довільній аналітичній формі. 2. У одержаній здійсненій НДФ проводять всі операції неповного склеювання і поглинання. В результаті виходить скорочена НДФ заданій функції. 3. Знаходять мінімальні НДФ по імплікантной матриці. Якщо кількість членів в скороченій НДФ невелике, то можна знайти тупикові форми методом випробування членів і вибрати серед них мінімальні. Операція неповного склеювання і поглинання для кон'юнктивної форми визначається відповідно наступними співвідношеннями: (x + y)(x +y) = x(x + y)(x +y), x(x + y) =...